David silver 强化学习 Lecture 2

课程主页： https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture2 的课程内容，这一讲简单介绍了马尔可夫决策过程。

马尔可夫过程

马尔可夫性

定义

状态$S_t$有马尔可夫性当且仅当

$$\mathbb{P}\left[S_{t+1} | S_{t}\right]=\mathbb{P}\left[S_{t+1} | S_{1}, \ldots, S_{t}\right]$$

• 状态从历史中捕获所有相关信息
• 一旦知道状态后，历史可以被丢弃
• 状态是未来的充分统计量

状态转移矩阵

对于马尔可夫状态$s$和后继状态$s’$，状态转移概率被定义为

$$\mathcal{P}_{s s^{\prime}}=\mathbb{P}\left[S_{t+1}=s^{\prime} | S_{t}=s\right]$$

状态转移矩阵$\mathcal P$定义了从所有状态$s$到后继状态$s’$的概率，

$$\mathcal{P}=\left[\begin{array}{ccc}{\mathcal{P}_{11}} & {\cdots} & {\mathcal{P}_{1 n}} \\ {\vdots} & {} & {\vdots} \\ {\mathcal{P}_{n 1}} & {\cdots} & {\mathcal{P}_{n n}}\end{array}\right]$$

不难看出该矩阵每行的和为$1$。

马尔可夫过程

马尔可夫过程是无记忆的随机过程，即一系列具有马尔可夫性的随机状态$\mathcal S_1,\mathcal S_2,\ldots$。

定义

马尔可夫过程（马尔可夫链）是元组$\langle\mathcal{S}, \mathcal{P}\rangle$

• $\mathcal S$是（有限）状态集合

• $\mathcal P$是状态转移概率矩阵：

  $$\mathcal{P}_{s s^{\prime}}=\mathbb{P}\left[S_{t+1}=s^{\prime} | S_{t}=s\right]$$

一个具体例子如下：

马尔可夫奖励过程

定义

马尔可夫奖励过程是元组$\langle\mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma\rangle$

• $\mathcal S$是（有限）状态集合

• $\mathcal P$是状态转移概率矩阵：

  $$\mathcal{P}_{s s^{\prime}}=\mathbb{P}\left[S_{t+1}=s^{\prime} | S_{t}=s\right]$$

• $\mathcal R$是奖励函数，$\mathcal{R}_{s}=\mathbb{E}\left[R_{t+1} | S_{t}=s\right]$

• $\gamma$是折扣因子，$\gamma \in[0,1]$

一个具体例子如下：

Return

定义

return $G_t$是从时间$t$开始的总折扣奖励：

$$G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}$$

为什么需要折扣因子

大多数马尔可夫奖励和决策过程都有折扣因子。 为什么？

• 数学上方便处理折扣奖励
• 避免循环马尔可夫过程中的无限回报
• 关于未来的不确定性可能无法完全体现
• 如果奖励是经济奖励，则即时奖励可能比延迟奖励赚取更多的利息
• 动物/人类行为显示出对即时奖励的偏好
• 有时可能会使用未折扣的马尔可夫奖励过程（即$\gamma =1$）

价值函数

价值函数$v(s)$给出状态$s$的长期价值

定义

MRP的状态价值函数$v(s)$是从状态$s$出发的return期望

$$v(s)=\mathbb{E}\left[G_{t} | S_{t}=s\right]$$

贝尔曼方程

由价值函数的定义，不难得到

$$\begin{aligned} v(s) &=\mathbb{E}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma\left(R_{t+2}+\gamma R_{t+3}+\ldots\right) | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) | S_{t}=s\right] \end{aligned}$$

上述等式表示价值函数可以被分解为两部分：

• 即时奖励$R_{t+1}$
• 后继状态的折扣奖励$\gamma v\left(S_{t+1}\right)$

利用状态转移矩阵，不难将上述方程改写为

$$v(s)=\mathcal{R}_{s}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}} v\left(s^{\prime}\right)$$

上述方程组被称为贝尔曼方程。

矩阵形式的贝尔曼方程

利用矩阵符号，很容易将贝尔曼方程改写为矩阵形式：

$$\left[\begin{array}{c}{v(1)} \\ {\vdots} \\ {v(n)}\end{array}\right]=\left[\begin{array}{c}{\mathcal{R}_{1}} \\ {\vdots} \\ {\mathcal{R}_{n}}\end{array}\right]+\gamma\left[\begin{array}{ccc}{\mathcal{P}_{11}} & {\cdots} & {\mathcal{P}_{1 n}} \\ {} & {} & {} \\ {\mathcal{P}_{n1}} & {\ldots} & {\mathcal{P}_{n n}}\end{array}\right]\left[\begin{array}{c}{v(1)} \\ {\vdots} \\ {v(n)}\end{array}\right]$$

即

$$\begin{aligned} v &=\mathcal{R}+\gamma \mathcal{P} v \\(l-\gamma \mathcal{P}) v &=\mathcal{R} \\ v &=(l-\gamma \mathcal{P})^{-1} \mathcal{R} \end{aligned}$$

马尔可夫决策过程

马尔可夫决策过程（MDP）是具有决策的马尔可夫奖励过程，环境中的所有状态都具有马尔可夫性。

定义

马尔可夫决策过程是元组$\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$

• $\mathcal S$是（有限）状态集合

• $\mathcal A$是有限动作集合

• $\mathcal P$是状态转移概率矩阵：

  $$\mathcal{P}_{s s^{\prime}}^a=\mathbb{P}\left[S_{t+1}=s^{\prime} | S_{t}=s,A_t =a\right]$$

• $\mathcal R$是奖励函数，$\mathcal{R}_{s}^a=\mathbb{E}\left[R_{t+1} | S_{t}=s,A_t =a\right]$

• $\gamma$是折扣因子，$\gamma \in[0,1]$

策略

定义

策略$\pi$是动作关于状态的条件分布：

$$\pi(a | s)=\mathbb{P}\left[A_{t}=a | S_{t}=s\right]$$

• 策略完全定义了智能体的行动

• MDP策略依赖于当前状态（不是历史）

• 给定MDP $\mathcal{M}=\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$以及策略$\pi$

• 状态序列$ S_1, S_2\ldots$是马尔可夫过程$\left\langle\mathcal{S}, \mathcal{P}^{\pi}\right\rangle$

• 状态和奖励序列$S_{1}, R_{2}, S_{2}, \ldots$是马尔可夫奖励过程$\left\langle\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma\right\rangle$

• 其中

  $$\begin{aligned} \mathcal{P}_{s, s^{\prime}}^{\pi} &=\sum_{a \in \mathcal{A}} \pi(a | s) \mathcal{P}_{s s^{\prime}}^{a} \\ \mathcal{R}_{s}^{\pi} &=\sum_{a \in \mathcal{A}} \pi(a | s) \mathcal{R}_{s}^{a} \end{aligned}$$

价值函数

定义

MDP的状态价值函数$v_\pi(s)$是从状态$s$出发，按照策略$\pi $的期望return：

$$v_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right]$$

定义

动作价值函数$q_{\pi}(s, a)$是从状态$s$出发，采取动作$a$，然后按照策略$\pi $的期望return：

$$q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[G_{t} | S_{t}=s, A_{t}=a\right]$$

贝尔曼方程

类似前一部分，不难得到状态价值函数以及动作价值函数的贝尔曼方程：

$$\begin{aligned} v_{\pi}(s)&=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right]\\ q_{\pi}(s, a)&=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, A_{t+1}\right) | S_{t}=s, A_{t}=a\right] \end{aligned}$$

另一方面，利用两者的关系，我们有：

$$v_{\pi}(s)=\sum_{a \in \mathcal{A}} \pi(a | s) q_{\pi}(s, a)$$

$$q_{\pi}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)$$

将上述等式再次代入可以得到新的等式：

$$v_{\pi}(s)=\sum_{a \in \mathcal{A}} \pi(a | s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)\right)$$

$$q_{\pi}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \sum_{a^{\prime} \in \mathcal{A}} \pi\left(a^{\prime} | s^{\prime}\right) q_{\pi}\left(s^{\prime}, a^{\prime}\right)$$

贝尔曼方程的矩阵形式

回顾方程

$$v_{\pi}(s)=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right]$$

将其表示为矩阵形式可得

$$v_{\pi}=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} v_{\pi}$$

直接求解得到

$$v_{\pi}=\left(I-\gamma \mathcal{P}^{\pi}\right)^{-1} \mathcal{R}^{\pi}$$

最优价值函数

定义

最优状态价值函数$v_\star (s)$是关于所有策略的最大值

$$v_{*}(s)=\max _{\pi} v_{\pi}(s)$$

最优动作价值函数$q_\star(s, a)$是动作-价值函数关于所有策略的最大值

$$q_{*}(s, a)=\max _{\pi} q_{\pi}(s, a)$$

• 最优价值函数指定了MDP中可能的最佳性能。
• 当我们知道最优值时，可以说MDP“已解决”。

最优策略

在策略上定义偏序

$$\pi \geq \pi^{\prime} \text { if } v_{\pi}(s) \geq v_{\pi^{\prime}}(s), \forall s$$

定理

对于任意马尔可夫决策过程

• 存在不比其他策略差的最优策略$\pi_\star$，即$\pi_{*} \geq \pi, \forall \pi$
• 所有最优策略达到最优价值函数，$v_{\pi_{}}(s)=v_{}(s)$
• 所有最优策略达到最优动作价值函数，$q_{\pi_{}}(s, a)=q_{}(s, a)$

找到最优策略

最优策略可以通过最大化$q_{*}(s, a)$来求解，

$$\pi_{*}(a | s)=\left\{\begin{array}{ll}{1} & {\text { if } a=\operatorname{argmax}_{a \in \mathcal{A}} q_{*}(s, a)} \\ {0} & {\text { otherwise }}\end{array}\right.$$

• 任何MDP始终都有确定性的最佳策略
• 如果我们知道$q_{\star}(s, a)$，我们将立即获得最优策略

$v_\star,q_\star$的贝尔曼方程

最优价值函数通过Bellman最佳方程递归相关：

$$v_{*}(s)=\max _{a} q_{*}(s, a)$$

$$q_{*}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)$$

$$v_{*}(s)=\max _{a} \mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)$$

$$q_{*}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \max _{a^{\prime}} q_{*}\left(s^{\prime}, a^{\prime}\right)$$

求解贝尔曼最优方程

• 贝尔曼最优方程是非线性的
• 没有封闭解（通常）
• 许多迭代求解方法
  • 价值迭代
  • 策略迭代
  • Q-learning
  • Sarsa

MDP的拓展

• 无限和连续的MDP
• 部分可观察的MDP
• 未折现的，平均奖励MDP